package com.shm.leetcode;

/**
 * 813. 最大平均值和的分组
 * 给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。
 *
 * 注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。
 *
 * 返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [9,1,2,3,9], k = 3
 * 输出: 20.00000
 * 解释:
 * nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
 * 我们也可以把 nums 分成[9, 1], [2], [3, 9].
 * 这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
 * 示例 2:
 *
 * 输入: nums = [1,2,3,4,5,6,7], k = 4
 * 输出: 20.50000
 *
 *
 * 提示:
 *
 * 1 <= nums.length <= 100
 * 1 <= nums[i] <= 104
 * 1 <= k <= nums.length
 *
 */
public class LargestSumOfAverages {

    /**
     * 方法一：动态规划
     * 命题：平均值和最大的分组的子数组数目必定是 kk。
     *
     * 证明：假设一种分组的子数组数目小于 kk，那么它必然有一个子数组的元素数目 c > 1c>1，即仍然可以进行切分。设该子数组的平均值为 mm，左侧第一个元素为 xx，那么将该子数组第一个元素切分之后，平均值和为 \dfrac{m \times c - x}{c - 1} + x = \dfrac{c}{c - 1} \times m + \dfrac{c-2}{c-1} \times x > m
     * c−1
     * m×c−x
     * ​
     *  +x=
     * c−1
     * c
     * ​
     *  ×m+
     * c−1
     * c−2
     * ​
     *  ×x>m，因此再次切分后平均值和会增加，所以平均值和最大的分组的子数组数目必定是 kk。
     *
     * 为了方便计算子数组的平均值，我们使用一个数组 \textit{prefix}prefix 来保存数组 \textit{nums}nums 的前缀和。我们使用 \textit{dp}[i][j]dp[i][j] 表示 \textit{nums}nums 在区间 [0, i-1][0,i−1] 被切分成 jj 个子数组的最大平均值和，显然 i \ge ji≥j，计算分两种情况讨论：
     *
     * 当 j = 1j=1 时，\textit{dp}[i][j]dp[i][j] 是对应区间 [0, i - 1][0,i−1] 的平均值；
     *
     * 当 j > 1j>1 时，我们将可以将区间 [0, i - 1][0,i−1] 分成 [0, x - 1][0,x−1] 和 [x, i - 1][x,i−1] 两个部分，其中 x \ge j-1x≥j−1，那么 \textit{dp}[i][j]dp[i][j] 等于所有这些合法的切分方式的平均值和的最大值。
     *
     * 因此转移方程为：
     *
     * \textit{dp}[i][j] = \begin{cases} \dfrac{\sum_{r = 0}^{i - 1}\textit{nums}[r]}{i}, & j = 1 \\ \max\limits_{x \ge j - 1} \{dp[x][j - 1] + \dfrac{\sum_{r = x}^{i - 1}\textit{nums}[r]}{i - x}\}, & j > 1 \end{cases}
     * dp[i][j]=
     * ⎩
     * ⎪
     * ⎪
     * ⎪
     * ⎨
     * ⎪
     * ⎪
     * ⎪
     * ⎧
     * ​
     *
     * i
     * ∑
     * r=0
     * i−1
     * ​
     *  nums[r]
     * ​
     *  ,
     * x≥j−1
     * max
     * ​
     *  {dp[x][j−1]+
     * i−x
     * ∑
     * r=x
     * i−1
     * ​
     *  nums[r]
     * ​
     *  },
     * ​
     *
     * j=1
     * j>1
     * ​
     *
     *
     * 假设数组 \textit{nums}nums 的长度为 nn，那么 \textit{dp}[n][k]dp[n][k] 表示数组 \textit{nums}nums 分成 kk 个子数组后的最大平均值和，即最大分数。
     *
     * Python3C++JavaC#CJavaScriptGolang
     *
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode.cn/problems/largest-sum-of-averages/solution/zui-da-ping-jun-zhi-he-de-fen-zu-by-leet-09xt/
     * @param nums
     * @param k
     * @return
     */
    public double largestSumOfAverages(int[] nums, int k) {
        int n  = nums.length;
        double[] sum = new double[n+1];
        for(int i=0;i<n;i++){
            sum[i+1]=sum[i]+nums[i];
        }

        double[][] dp = new double[n+1][k+1];
        for (int i = 1; i <= n; i++) {
            dp[i][1] = sum[i]/i;
        }

        for (int j = 2; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                for (int x = j-1; x < i; x++) {
                    dp[i][j] = Math.max(dp[i][j], dp[x][j-1]+(sum[i]-sum[x])/(i-x));
                }

            }

        }
        return dp[n][k];
    }

    public double largestSumOfAverages_1(int[] nums, int k) {
        int n  = nums.length;
        double[] sum = new double[n+1];
        for(int i=0;i<n;i++){
            sum[i+1]=sum[i]+nums[i];
        }

        double[][] dp = new double[n+1][k+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i,k) ; j++) {
                //仅一段
                if (j==1) dp[i][j] = sum[i]/i;
                //多段，枚举最后一段的起点
                else {
                    // 当要分为j段时（j>1），我们枚举最后一段的长度，而之前j-1段至少需要j-1个元素，所以我们应该从x=j-1开始枚举，而第j段至少需要有一个元素，所以x<i，
                    for (int x = j-1; x < i; x++) {
                        dp[i][j] = Math.max(dp[i][j], dp[x][j-1]+(sum[i]-sum[x])/(i-x));
                    }
                }
            }
        }
        
        return dp[n][k];
    }

    /**
     * 由于 \textit{dp}[i][j]dp[i][j] 的计算只利用到 j-1j−1 的数据，因此也可以使用一维数组对 \textit{dp}[i][j]dp[i][j] 进行计算，在计算过程中，要注意对 ii 进行逆序遍历。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(k \times n^2)O(k×n
     * 2
     *  )，其中 kk 是分组的最大子数组数目，nn 是数组 \textit{nums}nums 的长度。计算前缀和需要 O(n)O(n) 的时间，动态规划需要计算 O(k \times n)O(k×n) 个状态，每个状态的计算时间是 O(n)O(n)。
     *
     * 空间复杂度：O(k \times n)O(k×n) 或 O(n)O(n)，其中 kk 是分组的最大子数组数目，nn 是数组 \textit{nums}nums 的长度。二维数组实现的空间复杂度是 O(k \times n)O(k×n)，一维数组实现的空间复杂度是 O(n)O(n)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode.cn/problems/largest-sum-of-averages/solution/zui-da-ping-jun-zhi-he-de-fen-zu-by-leet-09xt/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode.cn/problems/largest-sum-of-averages/solution/zui-da-ping-jun-zhi-he-de-fen-zu-by-leet-09xt/
     * @param nums
     * @param k
     * @return
     */
    public double largestSumOfAverages_2(int[] nums, int k) {
        int n  = nums.length;
        double[] sum = new double[n+1];
        for(int i=0;i<n;i++){
            sum[i+1]=sum[i]+nums[i];
        }

        double[] dp = new double[n+1];
        for (int i = 1; i <= n; i++) {
            dp[i] = sum[i]/i;
        }

        for (int j = 2; j <= k; j++) {
            for (int i = n; i >= j; i--) {
                for (int x = j-1; x < i; x++) {
                    dp[i] = Math.max(dp[i], dp[x]+(sum[i]-sum[x])/(i-x));
                }

            }

        }
        return dp[n];
    }
}
